package Sort;

import java.util.Arrays;

/*
*归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
* 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
*
* */
public class MergeSort {

    static void ms(int[] nums){
        merge(nums,0, nums.length-1);

    }

    static void merge(int[] nums, int start, int end){
        //递归终止条件
        if(start>=end) return;
        int mid = start + ( end-start )/2;
        merge(nums,start,mid);
        merge(nums,mid+1,end);
        mergeTwo(nums,start,mid,end);
    }

    static void mergeTwo(int[] nums, int p, int q, int r){
        //初始化变量：i表示前半部分的下标，j表示后半部分的下标，k表示临时数组的下标
        int i = p;
        int j = q+1;
        int k = 0; //数组指针
        int[] tmp = new int[r-p+1]; //辅助数组
        //合并[p,q]和[q+1,r]的两个数组
        while(i<=q && j<=r){
            if(nums[i] > nums[j]){
                tmp[k++] = nums[j];
                j++;
            }else{
                tmp[k++] = nums[i];
                i++;
            }
        }
        for(;i<=q;i++){
            tmp[k++] = nums[i];
        }
        for (;j<=r;j++){
            tmp[k++] = nums[j];
        }
        //将tmp临时数组拷贝回原数组
        for(int x=0;x<r-p+1;x++) {
            nums[p+x]=tmp[x];
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,4,-1,-3,2,3};
        ms(nums);
        System.out.println(Arrays.toString(nums));
    }
}
